package org.example.code.test2024.nine_mouth;

import org.example.code.test2024.eight_mouth.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class test0904 {

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || root == p || root == q)
            return root;
        TreeNode left = lowestCommonAncestor(root.left,p,q);
        TreeNode right = lowestCommonAncestor(root.right,p,q);
        if(left != null && right != null)
            return root;
        return left != null ? left : right;
    }



    int max = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        maxPathSumHelper(root);
        return max;
    }
    private int maxPathSumHelper(TreeNode root) {
        if(root == null)
            return 0;
        int left = Math.max(maxPathSumHelper(root.left),0);
        int right = Math.max(maxPathSumHelper(root.right),0);
        int val = root.val + left + right;
        max = Math.max(max,val);
        return Math.max(left,right) + root.val;
    }


    public int orangesRotting(int[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
        int nr = grid.length;
        int nc = grid[0].length;
        int minutes = 0;
        Queue<int[]> q = new LinkedList<>();
        for (int r = 0; r < nr; ++r) {
            for (int c = 0; c < nc; ++c) {
                if (grid[r][c] == 2) {
                    q.offer(new int[]{r, c});
                }
            }
        }
        while (!q.isEmpty()&&!check(grid)) {
            int size = q.size();
            for (int i = 0; i < size; ++i) {
                int[] curr = q.poll();
                int r = curr[0];
                int c = curr[1];
                if (r > 0 && grid[r - 1][c] == 1) {
                    grid[r - 1][c] = 2;
                    q.offer(new int[]{r - 1, c});
                }
                if (r < nr - 1 && grid[r + 1][c] == 1) {
                    grid[r + 1][c] = 2;
                    q.offer(new int[]{r + 1, c});
                }
                if (c > 0 && grid[r][c - 1] == 1) {
                    grid[r][c - 1] = 2;
                    q.offer(new int[]{r, c - 1});
                }
                if (c < nc - 1 && grid[r][c + 1] == 1) {
                    grid[r][c + 1] = 2;
                    q.offer(new int[]{r, c + 1});
                }
            }
            ++minutes;
        }

        return check(grid)? minutes  : -1;
    }

    private boolean check(int[][] grid){
        for (int r = 0; r < grid.length; ++r) {
            for(int c = 0; c < grid[0].length; ++c) {
                if(grid[r][c] == 1)
                    return false;
            }
        }
        return true;
    }

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> adjList = new ArrayList<>();
        int[] inDegree = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            adjList.add(new ArrayList<>());
        }

        // 构建图和入度数组
        for (int[] prerequisite : prerequisites) {
            int course = prerequisite[0];
            int preCourse = prerequisite[1];
            adjList.get(preCourse).add(course);
            inDegree[course]++;
        }

        // 找到所有入度为0的节点
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }

        int[] order = new int[numCourses];
        int index = 0;

        // BFS遍历
        while (!queue.isEmpty()) {
            int current = queue.poll();
            order[index++] = current;

            for (int neighbor : adjList.get(current)) {
                inDegree[neighbor]--;
                if (inDegree[neighbor] == 0) {
                    queue.offer(neighbor);
                }
            }
        }

        // 如果结果中的课程数量不等于numCourses，说明存在循环依赖
        if (index != numCourses) {
            return false;
        }

        return true;
    }

    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        if (nums == null || nums.length == 0) {
            return res;
        }
        backtrack(nums, new ArrayList<>());
        return res;
    }
    private void backtrack(int[] nums, List<Integer> list) {
        if (list.size() == nums.length) {
            res.add(new ArrayList<>(list));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (list.contains(nums[i])) {
                continue;
            }
            list.add(nums[i]);
            backtrack(nums, list);
            list.remove(list.size() - 1);
        }
    }
    void dfs(char[][] grid, int r, int c) {
        int nr = grid.length;
        int nc = grid[0].length;

        if (r < 0 || c < 0 || r >= nr || c >= nc || grid[r][c] == '0') {
            return;
        }

        grid[r][c] = '0';
        dfs(grid, r - 1, c);
        dfs(grid, r + 1, c);
        dfs(grid, r, c - 1);
        dfs(grid, r, c + 1);
    }

    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }

        int nr = grid.length;
        int nc = grid[0].length;
        int num_islands = 0;
        for (int r = 0; r < nr; ++r) {
            for (int c = 0; c < nc; ++c) {
                if (grid[r][c] == '1') {
                    ++num_islands;
                    dfs(grid, r, c);
                }
            }
        }

        return num_islands;
    }
}
